# -*- coding:utf-8 -*-
# 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点

# 示例：
# 给定一个链表: 1->2->3->4->5, 和 n = 2
# 当删除了倒数第二个节点后，链表变为 1->2->3->5
# 说明：
# 给定的 n 保证是有效的

# 进阶：
# 你能尝试使用一趟扫描实现吗？

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

# # 实现一趟扫描
# class Solution(object):
#     def removeNthFromEnd(self, head, n):
#         """
#         :type head: ListNode
#         :type n: int
#         :rtype: ListNode
#         """
#         l_node = None;
#         r_index = 0;
#         r_node = ListNode(-1);
#         r_node.next = head;
#         head = r_node;
#         # self.printList(r_node.next);
#         while r_node.next:
#             if l_node:
#                 l_node = l_node.next;
#             r_node = r_node.next;
#             r_index += 1;
#             if r_index == n:
#                 l_node = head;
#         if l_node:
#             l_node.next = l_node.next.next;
#         # self.printList(head.next);
#         return head.next;

#     def printList(self, head):
#         current = head;
#         v_log = [];
#         while current:
#             v_log.append(current.val);
#             current = current.next;
#         print v_log;








# 同样一趟扫描，使代码逻辑更清晰，命名方式以及代码结构
# 注意！！！题目中给定的 n 保证是有效的，因而不用考虑n无效的问题
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        first_node = second_node = ListNode(-1);
        first_node.next = head;
        head = first_node;

        # node_num = 0;
        for i in xrange(0, n):
            if not first_node:
                break;
            first_node = first_node.next;
            # node_num += 1;

        while first_node.next:
            first_node = first_node.next;
            second_node = second_node.next;
            # node_num += 1;

        # if n > node_num or n <= 0:
        #     return head.next;

        second_node.next = second_node.next.next;
        return head.next;


    def printList(self, head):
        current = head;
        v_log = [];
        while current:
            v_log.append(current.val);
            current = current.next;
        print v_log;

head = ListNode(1);
current = head;
for i in xrange(2, 6):
    current.next = ListNode(i);
    current = current.next;

t = Solution();
t.removeNthFromEnd(head, 1);